package 剑指offer;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description:
 * @Author: Administrator
 * @Date: 2020-05-03
 */
public class 二叉树中和为某一值的路径 {

    public static ArrayList<ArrayList<Integer>> FindPath(TreeNode idol, int target) {

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        TreeNode root = idol;
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        ArrayList<Integer> road = new ArrayList<>();
        road.add(root.val);
        while (stack.size() != 0) {
            while (stack.peek().left != null &&
                    stack.peek().left != root && stack.peek().right != root) {
                stack.push(stack.peek().left);
                road.add(stack.peek().val);
            }
            if (stack.peek().right != null && stack.peek().right != root) {
                stack.push(stack.peek().right);
                road.add(stack.peek().val);
                continue;
            }


            root = stack.pop();
            System.out.println(root.val);
            if (isTarget(road, target) && root.left == null && root.right == null) {
                list.add(copyList(road));
            }
            if (road.size() > 0) {
                road.remove(road.size() - 1);
            }


        }
        return list;
    }

    public static void 先序遍历(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        System.out.println(root.val);
        while (!stack.isEmpty()) {
            while (root != null && root.left != null) {
                stack.push(root.left);
                System.out.println(root.left.val);
                root = root.left;
            }
            root = stack.pop();
            if (root.right != null) {
                System.out.println(root.right.val);
                stack.push(root.right);
                root = root.right;
            }

        }

    }

    public static boolean isTarget(List<Integer> list, int target) {
        int sum = 0;
        for (Integer integer : list) {
            sum += integer;
        }
        if (sum == target) {
            return true;
        }
        return false;
    }

    public static ArrayList copyList(ArrayList<Integer> list) {
        ArrayList temp = new ArrayList();
        for (Integer o : list) {
            temp.add(o);
        }
        return temp;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(1);

        print(FindPath(root, 19));
        先序遍历(root);

    }

    public void preTraverse(TreeNode root) {
        List<List> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (stack.size() != 0 && root != null) {
            while (stack.peek().left != null &&
                    stack.peek().left != root && stack.peek().right != root) {
                stack.push(stack.peek().left);
            }
            if (stack.peek().right != null && stack.peek().right != root) {
                stack.push(stack.peek().right);
                continue;
            }
            root = stack.pop();
            System.out.println(root.val);


        }
    }

    public static void print(ArrayList<ArrayList<Integer>> list) {
        for (List<Integer> integers : list) {
            for (Integer integer : integers) {
                System.out.print(integer + "\t");
            }
            System.out.println();
        }
    }


}
